/***
 * 以二叉链表作为二叉树的存储结构，交换二叉树中每个结点的左孩子和右孩子。

输入格式:
输入二叉树的先序序列。

提示：一棵二叉树的先序序列是一个字符串，若字符是‘#’,表示该二叉树是空树，否则该字符是相应结点的数据元素。

输出格式:
输出有两行：

第一行是原二叉树的中序遍历序列；

第二行是交换后的二叉树的中序遍历序列。

输入样例:
ABC##DE#G##F###

输出样例:
CBEGDFA

AFDGEBC
***/
#include "stdio.h"
#include "stdlib.h"
typedef struct biTree{
    char c;
    struct biTree *lchild,*rchild;
    struct biTree *parent;
}*BiTree,Node;
void CreateByPreOrder(BiTree *tree,Node *parent){
    Node *p;
    char c=getchar();
    if(c=='#'){
        if(tree==&(parent->lchild)){//是父节点的左分支，则转右分支
            CreateByPreOrder(&(parent->rchild),parent);
        }
        else{//是父节点的右分支，找祖先节点中有空右分支的结点
            p=parent->parent;
            if (!p)//已经找到根节点，并且已经确定右分支为空支，这棵树已经创建完成了
                return;
            while(p->rchild){
                p=p->parent;
                if(!p)
                    return; //已经找到根节点，并且已经确定右分支为空支，这棵树已经创建完成了
            }
            CreateByPreOrder(&(p->rchild), p);//找到了右支为空的结点，开始插入右分支
        }
    }else{
        //只要碰到的不是#，直接插入就好了
        Node *p = (Node *)malloc(sizeof(struct biTree));
        p->lchild = p->rchild = NULL;
        p->c=c;
        p->parent=parent;
        *tree=p;
        //已经插入结点，下个要处理的当然是左分支
        CreateByPreOrder(&(p->lchild), p);
    }
}
void SwapLRChild(BiTree t){
    Node *p;
    if (!t) return;//空树返回
    p=t->lchild;t->lchild=t->rchild;t->rchild=p;//交换左右分支
    SwapLRChild(t->lchild);SwapLRChild(t->rchild);//在孩子结点继续完成交换
}
void InOrder(BiTree t){
    if(!t)return;
    InOrder(t->lchild);
    printf("%c",t->c);
    InOrder(t->rchild);
}
int main(int argc, char const *argv[])
{
    BiTree t=NULL;
    CreateByPreOrder(&t,NULL);
    InOrder(t);
    printf("\n");
    SwapLRChild(t);
    InOrder(t);
    return 0;
}
